class Solution {
    public int jump(int[] nums) {
        if(nums.length==1) return 0;
        int farest=0;
        int left=0;
        int right=0;
        int cur=0;
        int ret=0;

        for(int i=0;i<nums.length;i++){
            farest=Math.max(i+nums[i],farest);
            if(i==cur){
                ret++;
                cur=farest;
                if(farest>=nums.length-1) return ret;
            }


        }

        return ret;


    }

}

public class T{
    public boolean func(int[] nums){
        if(nums.length==1) return true;
        int farest=0;
        int left=0;
        int right=0;
        int cur=0;
        int ret=0;

        while(left<=right){
            if(farest>=nums.length-1) return true;

            for(int i=left;i<=right;i++){
                farest=Math.max(i+nums[i],farest);
            }
            left=right+1;
            right=farest;
        }



        return false;
    }
}

class Solution2 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int step=0;
        int n=gas.length;
        if(n==1&&gas[0]-cost[0]>=0) return 0;
        int res=0;
        for(int i=0;i<n;i++){
            res=gas[i]-cost[i];
            if(res>0){
                step=1;

                while(res>=0){
                    int index=(i+step)%n;
                    res+=gas[index]-cost[index];
                    if(res<0) break;
                    step++;
                    if(step==n) break;
                }
                if(res>=0) return i;
                i=i+step;
            }

        }

        return -1;
    }
}




